Activité "Coloration de graphes"
DISPONIBLE
Un graphe est un objet mathématique composé de sommets, représentés par des points, reliés par des arêtes, représentées par des lignes (droites ou courbes). La coloration de graphe consiste à colorer chaque sommet du graphe de telle manière que deux sommets reliés par une arête n'ont pas la même couleur.
Découvrez et pratiquez la coloration de graphes qui n'est pas seulement un jeu d’enfant, mais aussi un outil puissant et polyvalent avec des applications allant de l’allocation de fréquences dans les réseaux à la planification d’emploi du temps.
Cette activité, qui peut se pratiquer en grandeur nature, sur plateau ou sur posters, permet de travailler de manière progressive le raisonnement logique et en particulier le fameux "si ... alors ...".
Cliquer sur l'image pour zoomer
Notions abordées
Graphe, coloration, algorithme, déduction logique.
Thématiques
Algorithmes dans les graphes,
Complexité,
Mathématiques discrètes,
Théorie des graphes
Niveau scolaire
cycle 2, cycle 3, cycle 4, lycée, supérieur
Audience grand public
adultes et enfants
Lieu d'utilisation
intérieur et extérieur
Contexte d'utilisation
tout contexte
Peut être empruntée ?
Oui
Matériel fourni
Pour un groupe d'une douzaine.
Grandeur nature : cerceaux (une douzaine), lattes (une soixantaine) et chasubles de couleur (une douzaine de chaque couleur).
Plateau : plateau avec potelets, élastiques et capuchons de couleur.
Poster : posters coloration et jetons de couleurs. (une vingtaine).
Durée
entre 10 et 30 minutes
Effectif encadrement minimum
1
Ressources nécessaires
aucune
Objectifs pédagogiques
- Comprendre la notion de graphe et ses capacités de modélisation.
- Travailler le raisonnement logique, en particulier le fameux "si ... alors ...".
- Travailler la notion d'algorithme.
Méthodologie
Les joueurs découvrent le jeu de coloration et ses applications avec des graphes installés sur le sol (avec des cerceaux et des lattes) ou dessinés sur des bâches. Ils peuvent jouer de manière collaborative en positionnant des objets de couleur sur les sommets et tenter de colorer les graphes de manière valide.
Pour cela, ils devront développer des raisonnements pour écarter des solutions non-valides, formaliser des algorithmes ou appliquer des algorithmes suggérés par l'animateur.
Plus de détails sur la fiche pédagogique.
Contacts
Dorian MAZAURIC
(dorian<dot>mazauric@inria<dot>fr)
Nicolas NISSE
(nicolas<dot>nisse@inria<dot>fr)
Incluse dans les parcours
Informations complémentaires